import java.util.*;
public class test {
    //leetcode 22.括号生成
    class Solution {
        public List<String> list;
        public StringBuilder path;
        public char[] str;
        public int left;
        public int right;

        public List<String> generateParenthesis(int n) {
            list = new ArrayList<>();
            path = new StringBuilder();
            str = new char[]{'(',')'};
            left = n;
            right = n;
            dfs(n, 0);
            return list;
        }

        public void dfs(int n, int index) {
            if (path.length() == n * 2) {
                list.add(path.toString());
                return;
            }
            for (int i = 0; i < 2; i++) {
                if (i == 0 && left > 0) {
                    path.append(str[i]);
                    left--;
                    dfs(n, index + 1);
                    path.deleteCharAt(path.length() - 1);
                    left++;
                }
                if (i == 1 && right > left) {
                    path.append(str[i]);
                    right--;
                    dfs(n, index + 1);
                    path.deleteCharAt(path.length() - 1);
                    right++;
                }
            }
        }
    }
    //leetcode 77.组合
    class Solution {
        public List<List<Integer>> list;
        public List<Integer> path;
        public int size;
        public List<List<Integer>> combine(int n, int k) {
            list = new ArrayList<>();
            path = new ArrayList<>();
            size = k;
            dfs(n,1);
            return list;
        }
        public void dfs(int n,int index){
            if(path.size() == size){
                list.add(new ArrayList<>(path));
                return;
            }
            for(int i = index;i <= n;i++){
                path.add(i);
                dfs(n,i + 1);
                path.remove(path.size() - 1);
            }
        }
    }
    //leetcode 17.电话号码的字母组合
    class Solution {
        public List<String> list;
        public StringBuilder path;
        public String[] str = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        public List<String> letterCombinations(String digits) {
            list = new ArrayList<>();
            path = new StringBuilder();
            if(digits.length() == 0){
                return list;
            }
            dfs(digits,0);
            return list;
        }
        public void dfs(String digits,int index){
            if(path.length() == digits.length()){
                list.add(path.toString());
                return;
            }
            String s = str[digits.charAt(index) - '0'];
            for(int i = 0;i < s.length();i++){
                path.append(s.charAt(i));
                dfs(digits,index + 1);
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}
